package leetcode.sword;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 用一个m*n的格子，0标识未到，1标识访问过了
 */
public class Solution13 {

    public static void main(String[] args) {
        System.out.println(new Solution13().movingCount(3,2,17));
    }

    //BFS
    public int movingCount(int m, int n, int k) {
        int[][] matrix = new int[m][n];
        int count = 0;
        Queue<int[]> next = new LinkedList<>();
        next.offer(new int[]{0,0});
        matrix[0][0] = 1;
        count++;
        while (!next.isEmpty()){
            //出队统计
            int[] ij = next.poll();
            int i = ij[0], j = ij[1];
            //相邻满足条件者入队
            if(i-1>=0&&matrix[i-1][j]==0&&ditSum(i-1)+ditSum(j)<=k) {
                next.offer(new int[]{i-1,j});
                matrix[i-1][j] = 1;
                count++;
            }
            if(i+1<m&&matrix[i+1][j]==0&&ditSum(i+1)+ditSum(j)<=k) {
                next.offer(new int[]{i+1,j});
                matrix[i+1][j] = 1;
                count++;
            }
            if(j-1>=0&&matrix[i][j-1]==0&&ditSum(i)+ditSum(j-1)<=k) {
                next.offer(new int[]{i,j-1});
                matrix[i][j-1] = 1;
                count++;
            }
            if(j+1<n&&matrix[i][j+1]==0&&ditSum(i)+ditSum(j+1)<=k) {
                next.offer(new int[]{i,j+1});
                matrix[i][j+1] = 1;
                count++;
            }
        }
        return count;
    }

//    public void backTrace(int[][] matrix, int m, int n, int i, int j, int k){
//        //先判断是否越界
//        if(i<0||i>=m||j<0||j>=n) return;
//        //判断是否已访问过
//        if(matrix[i][j]==1) return;
//        //判断是否可达
//        int tmp;
//        if(matrix[i][j]==-1||(tmp=ditSum(m)+ditSum(n))>k){
//            matrix[i][j]=-1;
//            return;
//        }
//        //
//    }

    public int ditSum(int num){
        int res = 0;
        while (num!=0){
            res += num%10;
            num /= 10;
        }
        return res;
    }
}
